﻿#define _CRT_SECURE_NO_WARNNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<iostream>
#include<cmath>
using namespace std;
//求出[a,b]区间内有多少个数数位之和为5的倍数
//int fun(int n)
//{
//	int sum = 0;
//	while (n)
//	{
//		sum += n % 10;
//		n /= 10;
//	}
//	return sum;
//}
//int main()
//{
//	long a, b;
//	cin >> a >> b;
//	if (a > b)
//	{
//		int temp = a;
//		a = b;
//		b = temp;
//	}
//	int sum = 0;
//	int count = 0;
//	for (int i = a; i <= b; i++)
//	{
//		if (fun(i) % 5 == 0)
//		{
//			count++;
//			cout << i << " ";	
//		}
//	}
//	cout << endl;
//	cout << "一共有" << count << "个" << endl;
//	return 0;
//}
//----------------------------------------
/*
今天牛牛学到了回文串，他想在数字里面找回文，即回文数，回文数是正着读与倒着读都一样的数，
比如1221，343是回文数，433不是回文数。请输出不超过n的回文数*/
//bool fun(int n)
//{
//	int sum = 0;
//	int a = n;
//	while (n)
//	{
//		sum = sum * 10 + n % 10;
//		n /= 10;
//		if (sum == a)
//		{
//			return true;
//		}
//	}
//	return false;
//}
//int main()
//{
//	long n;
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		if (fun(i))
//		{
//			cout << i << endl;
//		}
//	}
//	return 0;
//}
//----------------------------------------------------
//输出1~n中能被3整除，且至少有一位数字是5的所有整数.
//bool fun(int n)
//{
//	int a = 0;
//	while (n)
//	{
//		a = n % 10;
//		n /= 10;
//		if (a == 5)
//		{
//			return true;
//		}
//	}
//	return false;
//}
//long n;
//int main()
//{
//	cin >> n;
//	for (int i = 3; i <= n; i++)
//	{
//		if (i % 3 == 0 && fun(i))
//		{
//			cout << i << endl;
//		}
//	}
//	return 0;
//}
//-------------------------------------
//编程找出小于n的四位数ABCD中满足下述关系的数：
//（ＡＢ＋ＣＤ）∗（ＡＢ＋ＣＤ）＝ＡＢＣＤ
//int n;
//bool Is_Vatal(int n)
//{
//	int count = 0;
//	while (n)
//	{
//		count++;
//		n /= 10;
//	}
//	if (count == 4)
//	{
//		return true;
//	}
//	return false;
//}
//int main()
//{
//	cin >> n;
//	//判断是否是四位数
//	if (!Is_Vatal(n))
//	{
//		return 0;
//	}
//	for (int i = 1000; i <= n; i++)
//	{
//		int a = i / 1000;
//		int b = i / 100 % 10;
//		int c = i / 10 % 10;
//		int d = i % 10;
//		if ((a * 10 + b+c*10+d) * (a * 10 + b+c*10+d) == i)
//		{
//			cout << i << endl;
//		}
//	}
//	return 0;
//}
//--------------------------------------------------------
//求自然数N的所有约数之和
//long n;
//int main()
//{
//	cin >> n;
//	int sum = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		if (n % i == 0)
//		{
//			sum += i;
//		}
//	}
//	cout << sum << endl;
//	return 0;
//}
//------------------------------------------
//汉字的判断
//int main()
//{
//	char name;
//	cin >> name;
//	if (name < '0')
//	{
//		printf("Yes");
//	}
//	else
//	{
//		printf("No");
//	}
//}
//-----------------------------------------------
//输入一串字符，以“?”结束。统计其中字母个数，数字个数，其它符号个数
//#include<stdio.h>
//int main()
//{
//    char c;
//    int number = 0;
//    int letter = 0;
//    int other = 0;
//    while ((c = getchar()) != '?')
//    {
//        if (c >= '0' && c <= '9')
//        {
//            number++;
//        }
//        else if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
//        {
//            letter++;
//        }
//        else
//        {
//            other++;
//        }
//    }
//    printf("Letters=%d\n", letter);
//    printf("Digits=%d\n", number);
//    printf("Others=%d\n", other);
//    return 0;
//}
//---------------------------------------------------------------
//数字三角形
/* 输入4
1
2   3
4   5   6
7   8   9  10  */
//long  n;
//int main()
//{
//	cin >> n;
//	int a = 1;
//	for (int i = 1; i <= 4; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			cout << a<<" ";
//			a++;
//		}
//		cout << endl;
//	}
//	return 0;
//}
//---------------------------------
//字符金字塔
//输入：C，保证是大写
/*输出：
  A
 ABA
ABCBA  */
//int main()
//{
//	char c;
//	cin >> c;
//	if (c >= 'A' && c <= 'Z')
//	{
//		for (int i = 'A'; i <= c; i++)
//		{
//			//空格
//			for (int j = c - 'A'; j >= 'A'; j--)
//			{
//				cout << " ";
//			}
//			//打印A~c
//			for (int j = 'A'; j <= c; j++)
//			{
//				cout << (char)j;
//			}
//			//打印c-1~A
//			for (int j = c - 'A'; j >= 'A'; j--)
//			{
//				cout << (char)j;
//			}
//			cout << endl;
//		}
//	}
//	else
//	{
//		printf("输人错误\n");
//	}
//}
//-------------------------------------------
//字符金字塔
//int main()
//{
//	char c;
//	cin >> c;
//	if (c >= 'A' && c <= 'Z')
//	{
//		for (int i = 1; i <= c - 'A' + 1; i++)
//		{
//			for (int j = 1; j <= c - 'A'+1-i; j++)
//			{
//				cout << " ";
//			}
//			for (int j = 1; j <= i; j++)
//			{
//				cout << (char)('A' + j - 1);
//			}
//			for (int j = i-1; j >= 1; j--)
//			{
//				cout << (char)('A' + j - 1);
//			}
//			cout << endl;
//		}
//	}
//	return 0;
//}
//--------------------------------------------------
//约瑟夫环
//int main()
//{
//	int number, k;
//	int m = 0;
//	cin >> number>> k;
//	int arr[10002];
//	int n = number;
//	int pos = 0;
//	int count = 1;
//	for (int i = 1; i <= n; i++)
//	{
//		arr[i - 1] = i;
//	}
//	while (number > 1)
//	{
//		if (arr[pos] > 0)
//		{
//			if (count == k)
//			{
//				arr[pos] = 0;
//				number--;
//				count = 1;
//				pos = (++pos) % n;
//			}
//			else
//			{
//				count++;
//				pos = (++pos) % n;
//			}
//		}
//		else
//		{
//			pos = (++pos) % n;
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		if (arr[i] > 0)
//		{
//			cout << arr[i] << endl;
//		}
//	}
//	return 0;
//}
//-------------------------------------------
//BF算法
//int main()
//{
//	char str1[10001];
//	char str2[10001];
//	scanf_s("%s", str1);
//	getchar();
//	scanf_s("%s", str2);
//	int i = 0;
//	int j = 0;
//	/*int len1=strlen(str1);
//	int len2=strlen(str2);*/
//	while (str1[i]!='\0' && str2[j]!='\0')
//	{
//		if (str1[i] == str2[j])
//		{
//			i++;
//			j++;
//		}
//		else
//		{
//			j = 0;
//			i++;
//		}
//	}
//	if (str2[j] == '\0')
//	{
//		printf("Yes\n");
//	}
//	else
//	{
//		printf("No\n");
//	} 
//	return 0;
//}
//-----------------------------------------
/*
牛村村口要架设一个矩形的广告屏，村长要求广告屏的总像素必须为n，
还要求广告屏的长和宽最大可能的接近，而且宽不能大于长，村长找你来计算一下宽和长分别为多少？*/
//long n;
//int main()
//{
//	cin >> n;
//	int a, b;
//	int mid = n / 2;
//	int min = 100000;
//	int max = -100000;
//	for (a = 1; a < mid; a++)
//	{
//		for (b = mid ; b < n; b++)
//		{
//			if (a * b == n)
//			{
//				if (a < min)
//				{
//					min = a;
//				}
//				if (b > max)
//				{
//					max = b;
//				}
//			}
//		}
//	}
//	cout << min << " " << max;
//	return 0;
//}
//----------------------------------------
//广告屏幕
//long n;
//int main()
//{
//	cin >> n;
//	int max = -1010;
//	for(int i = 1; i <= sqrt(n); i++)
//	{
//		if (n % i == 0)
//		{
//			max = i;
//		}
//	}
//	cout << max << " " << n / max;
//	return 0;
//}
//----------------------------------------
/*
牛可乐在牛牛商场买了一个帽子，要支付c元金币，牛牛商场一律不找零钱，
牛可乐手里有不限数量的面值a元的金币和面值b元的金币，请问牛可乐可以用金币刚好凑出总价c元吗？*/

//int main()
//{
//	int a, b, c;
//	cin >> c >> a >> b;
//	for (int i = 0; i <= c / b; i++)
//	{
//		if ((c - a * i) % b == 0)
//		{
//			cout << "Yes\n";
//			return 0;
//		}
//	}
//	cout << "No\n";
//	return 0;
//}
//------------------------------------------------
//最大公约数
//暴力法
//int main()
//{
//	long m, n;
//	cin >> m >> n;
//	int min = m > n ? n : m;
//	int temp = min;
//	int max = -9999;
//	for (int i = 1; i <= temp; i++)
//	{
//		if (n % i == 0 && m % i == 0)
//		{
//			if (max <  i)
//			{
//				max = i;
//			}
//		}
//	}
//	cout << max;
//	return 0;
//}
//-------------------------------
//辗转相除法
//int main()
//{
//	int n, m;
//	cin >> m >> n;
//	if (m < n)
//	{
//		int temp = n;
//		n = m;
//		m = temp;
//	}
//	int r = m % n;
//	while (r != 0)
//	{
//		m = n;
//		n = r;
//		r = m % n;
//	}
//	int i = n;
//	cout << i;
//	return 0;
//}
//---------------------------------
//链表
//#define ElemType int
//typedef struct Node
//{
//	ElemType data;
//	struct Node* next;
//}Node,*Link;
//Link Create()
//{
//	Link head = (Link)malloc(sizeof(Node));
//	assert(head);
//	head->next = NULL;
//	return head;
//}
//void Create_1(Link head)
//{
//	ElemType elem;
//	int n = 0;
//	cin >> n;
//	Link rear = head;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> elem;
//		Link node = (Link)malloc(sizeof(Node));
//		assert(node);
//		node->data = elem;
//		node->next = NULL;
//		rear->next = node;
//		rear = node;
//	}
//}
//void Show(Link head)
//{
//	if (head->next == NULL)
//	{
//		return;
//	}
//	Link p = head->next;
//	while (p)
//	{
//		cout << p->data << " ";
//		p = p->next;
//	}
//	cout << endl;
//}
//
//void Create_2(Link head)
//{
//	int n;
//	cin >> n;
//	ElemType elem;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> elem;
//		Link node = (Link)malloc(sizeof(Node));
//		assert(node);
//		node->data = elem;
//		node->next = head->next;
//		head->next = node;
//	}
//}
//int main()
//{																		  
//	Link head = Create();
//	Create_2(head);
//	Show(head);
//	return 0;
//}
//----------------------------------------
//int main()
//{
//	char s[100];
//	fgets(s,100,stdin);
//	cout << s;
//	return 0;
//}
//--------------------------------------
int main()
{
	
	return 0;
}